package _interview150;

/**
 * 121. 买卖股票的最佳时机
 */
public class No121 {
    private int[] prices;
    private int[][][] cache;

    /**
     * 1.递归
     */
    public int maxProfit1(int[] prices) {
        this.prices = prices;
        int n = prices.length;
        cache = new int[n][2][2];
        for (int i = 0; i < n; i++) {
            cache[i][0][0] = -1;
            cache[i][0][1] = -1;
            cache[i][1][0] = -1;
            cache[i][1][1] = -1;
        }
        return dfs(n - 1, 0, 1);
    }

    private int dfs(int i, int hold, int j) {
        if (j < 0) return Integer.MIN_VALUE;
        else if (i < 0) return hold == 0 ? 0 : Integer.MIN_VALUE;
        else if (cache[i][hold][j] != -1) return cache[i][hold][j];
        else if (hold == 0) return cache[i][hold][j] = Math.max(dfs(i - 1, 0, j), dfs(i - 1, 1, j - 1) + prices[i]);
        else return cache[i][hold][j] = Math.max(dfs(i - 1, 1, j), dfs(i - 1, 0, j) - prices[i]);
    }

    /**
     * 2.贪心
     */
    public int maxProfit2(int[] prices) {
        int min = Integer.MAX_VALUE;
        int ans = 0;
        for (int price : prices) {
            if (price < min) min = price;
            else ans = Math.max(price - min, ans);
        }
        return ans;
    }
}
